package PersonStu.sanqi;

import com.sun.media.sound.SoftTuning;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;

/**
 * @Author: Dijah
 * @Date: 2022/12/12 9:57
 * @Desc:
 * 给定两个字符串s1和s2，问s2最少删除多少字符可以成为s1的子串？
 * s1 = "abcde"; s2 = "axbc";
 */
public class code_12_DeleteMinCost {

    public static int minCost(String s1,String s2){
        List<String> subS2 = new ArrayList<String>();
        //找出所有上s2的子序列
        process(s2.toCharArray(),0,"",subS2);
        //按照长度排序，长度长的排到前面。
        subS2.sort(new com());
        for (String str : subS2) {
            if(s1.indexOf(str) != -1){
                return s2.length() - str.length();
            }
        }
        return s2.length();

    }

    /**
     * 生成一个字符串的子序列
     * @param str2
     * @param index
     * @param path
     * @param list
     */
    private static void process(char[] str2, int index, String path, List<String> list) {
        if(index == str2.length){
            list.add(path);
            return;
        }
        //嫑index+1的位置
        process(str2,index + 1,path,list);
        //要index位置的字符
        process(str2,index + 1,path + str2[index],list);

    }

    public static class com implements Comparator<String> {

        @Override
        public int compare(String s1,String s2) {
            return s2.length() - s1.length();
        }
    }

    public static void main(String[] args) {
        String s1 = "abcde";
        String s2 = "axbc";
        int i = minCost(s1, s2);
        System.out.println(i);
    }
}
